package com.aqie.medium.backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 131 分割回文串， 每个子串都是回文串
 */
public class Partition {
    List<List<String>> res=new ArrayList<>();

    /**
     * 1. 回溯算法  15ms
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        if(s.equals("") ||s.length()==0){
            return res;
        }
        List<String> list=new ArrayList<>();
        backTracing(list,s,0);
        return res;
    }


    private void backTracing(List<String> list, String s, int i){
        if(i==s.length()){
            res.add(list);
        }
        for(int j=i+1;j<=s.length();++j){
            if(isPalindrome(s.substring(i,j))){
                list.add(s.substring(i,j));
                backTracing(new ArrayList<>(list),s,j);
                list.remove(list.size()-1);
            }
        }
    }



    private boolean isPalindrome(String s){   //判断是否为回文串
        if(s.equals("") ||s.length()==0){
            return false;
        }
        int len=s.length();
        for(int i=0;i<=len/2;++i){
            if(s.charAt(i)!=s.charAt(len-1-i)){
                return false;
            }
        }
        return true;
    }


    /**
     * 2,回溯 + DFS  6ms
     */
    List<List<String>> list=new ArrayList<>();
    private String s;
    public List<List<String>> partition2(String s) {
        //从头到尾递归+回溯。
        this.s=s;
        //这个是满足的每一个集合
        List<String>ll=new ArrayList<>();
        dfs(ll,0);
        return list;
    }
    public void dfs(List<String>ll,int index){
        if(index==s.length())
        {
            list.add(new ArrayList<>(ll));
            return;
        }
        //i从index开始是因为单个字符也是回文子串
        for(int i=index;i<s.length();i++)
        {
            //如果是回文
            if(isPalindrome(index,i)){

                //把当前的回文子串s(index,i)加进去
                ll.add(s.substring(index,i+1));
                dfs(ll,i+1);
                //把加进去的回文子串去处。和上面加进去的回文子串是同一个回文子串。
                ll.remove(ll.size()-1);
            }

        }
    }
    private boolean isPalindrome(int start, int end){
        while(start<end){
            if(s.charAt(start)!=s.charAt(end))
                return false;
            start++;
            end--;
        }
        return true;
    }


    /**
     * 3. DP + DFS  7ms
     * @param s
     * @return
     */
    public List<List<String>> partition3(String s) {
        List<List<String>> res = new ArrayList<>();
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1])) dp[j][i] = true;
            }
        }
        System.out.println(Arrays.deepToString(dp));
        dfs(res, dp, 0, n, s, new ArrayList<String>());
        return res;

    }

    private void dfs(List<List<String>> res, boolean[][] dp, int i, int n, String s, ArrayList<String> tmp) {
        if (i == n) res.add(new ArrayList<>(tmp));
        for (int j = i; j < n; j++) {
            if (dp[i][j]) {
                tmp.add(s.substring(i, j + 1));
                dfs(res, dp, j + 1, n, s, tmp);
                tmp.remove(tmp.size() - 1);
            }
        }
    }



}
